# urandom 300 solution (crappy one)
# Defcon 20 CTF: urandom 300
# http://securityblackswan.blogspot.com
import binascii
import struct
import time

# qsort implementation
# http://en.literateprograms.org/Quicksort_(Python)
def qsort1(list):
    if list == []: 
        return []
    else:
        pivot = list[0]

        lesser = qsort1([x for x in list[1:] if x < pivot])
        greater = qsort1([x for x in list[1:] if x >= pivot])
        return lesser + [pivot] + greater

# This function returns the "swap" moves that will order an unordered array. It requires the original array (unordered) and the final array (ordered)
# Note: This function is 'crap' code, and it has some bugs that might arise under specific unordered lists
def getSwapMoves(initial,ordered):
    counter=0
    data=''
    # We create a dict in order to have quick lookups
    dictInitial=dict()
    for j in range(0,len(initial)):
        valor=initial[j]
        if dictInitial.has_key(valor) == False:
            dictInitial[valor]=list()
            dictInitial[valor].append(j)
        else:
            dictInitial[valor].append(j)
            dictInitial[valor].sort()
            dictInitial[valor].reverse()

    # For each ordered value, we find a "swap" move that needs to be done on the unordered array
    for pos_final in range(0,len(ordered)-1):
        numero=ordered[pos_final]
        lista_i=dictInitial[numero]
        if ordered[pos_final]==initial[pos_final]:
            continue

        # i->j
        pos_original=lista_i.pop()
        # Change value of j (pos_final)
        num_j=initial[pos_final]
        list_j=dictInitial[num_j]
        myindex=list_j.index(pos_final)
        list_j[myindex]=pos_original
        # Change value of i (pos_orig)
        dictInitial[num_j].sort()
        lista_i.append(pos_final)
        dictInitial[numero].sort()
        # Keep changes also on original_list
        aux=initial[pos_final]
        initial[pos_final]=initial[pos_original]
        initial[pos_original]=aux
        counter+=1
        data += str(pos_original)+":"+str(pos_final)+"\n"

    return counter,data


# This function will check that the steps provided on the file 'steps.txt' will generate a valid ordered array
def verifySteps(mylist,ordered,myfile="steps.txt"):
  
    fp=open(myfile,'r')
    for line in fp.readlines():
        #print line
        aux=line.strip("\n").split(':')
        #print aux
        i=int(aux[0])
        j=int(aux[1])
        aux=mylist[j]
        mylist[j]=mylist[i]
        mylist[i]=aux        
    fp.close()
    counter=0
    for i in range(0,len(mylist)):
        if (mylist[i] <> ordered[i]):
            print "\t[ERROR] Error!: "  + "["+str(i)+"] "+ str(mylist[i]) + " vs " + str(ordered[i])
            counter+=1
    return counter        
 

    
# Main function that will generate the solution (steps.txt) for an unsorted list.
def generateSteps(mylist,myfile="steps.txt"):
    t1=time.time()
    original=list(mylist)
    copiamylist=list(mylist)
    ordered=list(mylist)
    ordered=qsort1(ordered)

    (counter,data)= getSwapMoves(mylist,ordered)
    fp=open(myfile,'w+')
    for i in data:
        fp.write(i)
    fp.close()
    t2=time.time()
    print "	[DEBUG] Solution generated and verified in " + str(t2-t1) + " seconds"
    
def doIT_quick():
    fp=open('digits','rb')
    data=fp.read()
    fp.close()
    mylist=list()
    mylistb=list(mylist)
    print("	[DEBUG] " + str(len(data)) + " digits read")
    for i in range(0,len(data)/2):
        #num=struct.unpack("<H", data[i*2:i*2+2])[0]
        num=struct.unpack("<H", data[i*2:i*2+2])[0]
        mylist.append(num)
    generateSteps(mylist)
    
    
# quick and dirty function to verify the solution obtained by the previous program 
def test_generic(f1,f2):
    mylist=readNumbers(f1)
    ordered=list(mylist)
    ordered=qsort1(ordered)
    errors= verifySteps(mylist,ordered,f2)
    if (errors==0):
        print("\t[DEBUG] No errors found, well done :)")
        print("\t[DEBUG] Sorted in " + str(len(mylist)) + " moves. A good solution will require around ~100k steps/swap moves")
    else:
        print("\t[DEBUG] " + str(errors) + " errors found, :(")

# quick and dirty function to read digits from a file    
def readNumbers(myfile="datadump.dmp"):
    fp=open(myfile,'rb')
    data=fp.read()
    fp.close()
    mylist=list()
    for i in range(0,len(data)/2):
        #num=struct.unpack("<H", data[i*2:i*2+2])[0]
        num=struct.unpack("<H", data[i*2:i*2+2])[0]
        mylist.append(num)
    return mylist

print "[INFO] Creating solution for unsorted list stored on 'digits' file. Output -> steps.txt file"
doIT_quick()
print "\n[INFO] Verifying that the solution (steps.txt) is correct"
test_generic('digits','steps.txt')
